package week_04;

import java.util.ArrayList;
import java.util.List;

/**
 * 实现小根二叉堆
 * 实现方法
 * pop(): 弹出堆顶
 * insert(): 加入元素
 * delete(ListNode node): 删除任意节点元素
 * <p>
 * 基础操作--调整节点位置：
 * heapifyDown(): 向下调整位置
 * heapifyUp(): 向上调整位置
 */
public class BinaryHeap_b1 {
    List<ListNode> heapList;
    int size;

    public BinaryHeap_b1() {
        heapList = new ArrayList<>();
        size = 0;
    }

    public ListNode pop() {
        ListNode top = heapList.get(0);
        //尾节点替换到堆顶
        heapList.add(0, heapList.get(size - 1));
        heapList.remove(size - 1);
        size--;
        //再向下调整
        heapifyDown(0);
        return top;
    }

    public void insert(int value) {
        ListNode node = new ListNode(value);
        heapList.add(node);
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int child) {
        // 一路向上跟父节点比较，直到满足堆性质，小于父节点停止
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (heapList.get(child).val - heapList.get(parent).val > 0) {
                swap(parent, child);
            } else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    private void heapifyDown(int parent) {
        // 跟左右节点比较 找到下一个child
        // 调整知道满足堆特性
        int child = parent * 2 + 1;
        while (child < size) {
            int anotherChild = parent * 2 + 2;
            if (anotherChild < size &&
                    heapList.get(anotherChild).val - heapList.get(child).val > 0) child = anotherChild;
            if (heapList.get(parent).val - heapList.get(child).val < 0) {
                swap(parent, child);
            } else {
                break;
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }

    public void swap(int i, int j) {
        ListNode tmp = heapList.get(j);
        heapList.set(j, heapList.get(i));
        heapList.set(i, tmp);
    }


}
